package sol.leetcode;

import def.TreeNode;

/**
 * Flatten Binary Tree to Linked List
 */
public class Issue114 {
    public void flatten(TreeNode root) {
        flat(root);
    }

    private TreeNode flat(TreeNode root) {
        if (root == null)
            return root;

        TreeNode leftList = flat(root.left);
        TreeNode rightList = flat(root.right);
        root.right = leftList;
        root.left = null;
        TreeNode p = root;
        while (p.right != null)
            p = p.right;
        p.right = rightList;
        return root;
    }

    public static void main(String[] args) {
        TreeNode n1 = new TreeNode(1);
        TreeNode n2 = new TreeNode(2);
        TreeNode n3 = new TreeNode(3);
        TreeNode n4 = new TreeNode(4);
        TreeNode n5 = new TreeNode(5);
        TreeNode n6 = new TreeNode(6);

        n1.left = n2;
        n1.right = n5;
        n2.left = n3;
        n2.right = n4;
        n5.right = n6;

        Issue114 sol = new Issue114();
        sol.flatten(n1);

        while (n1 != null) {
            System.out.println(n1.val);
            n1 = n1.right;
        }
    }
}
